{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Last Day Where You Can Still Cross"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #array #binary-search #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #数组 #二分查找 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: latestDayToCross"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #你能穿过矩阵的最后一天"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>1</strong>&nbsp;开始的二进制矩阵，其中&nbsp;<code>0</code>&nbsp;表示陆地，<code>1</code>&nbsp;表示水域。同时给你&nbsp;<code>row</code> 和&nbsp;<code>col</code>&nbsp;分别表示矩阵中行和列的数目。</p>\n",
    "\n",
    "<p>一开始在第&nbsp;<code>0</code>&nbsp;天，<strong>整个</strong>&nbsp;矩阵都是&nbsp;<strong>陆地</strong>&nbsp;。但每一天都会有一块新陆地被&nbsp;<strong>水</strong>&nbsp;淹没变成水域。给你一个下标从&nbsp;<strong>1</strong>&nbsp;开始的二维数组&nbsp;<code>cells</code>&nbsp;，其中&nbsp;<code>cells[i] = [r<sub>i</sub>, c<sub>i</sub>]</code>&nbsp;表示在第&nbsp;<code>i</code>&nbsp;天，第&nbsp;<code>r<sub>i</sub></code>&nbsp;行&nbsp;<code>c<sub>i</sub></code>&nbsp;列（下标都是从 <strong>1</strong>&nbsp;开始）的陆地会变成 <strong>水域</strong>&nbsp;（也就是 <code>0</code>&nbsp;变成 <code>1</code>&nbsp;）。</p>\n",
    "\n",
    "<p>你想知道从矩阵最 <strong>上面</strong>&nbsp;一行走到最 <strong>下面</strong>&nbsp;一行，且只经过陆地格子的 <strong>最后一天</strong>&nbsp;是哪一天。你可以从最上面一行的&nbsp;<strong>任意</strong>&nbsp;格子出发，到达最下面一行的&nbsp;<strong>任意</strong>&nbsp;格子。你只能沿着&nbsp;<strong>四个</strong>&nbsp;基本方向移动（也就是上下左右）。</p>\n",
    "\n",
    "<p>请返回只经过陆地格子能从最 <strong>上面</strong>&nbsp;一行走到最 <strong>下面</strong>&nbsp;一行的 <strong>最后一天</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/07/27/1.png\" style=\"width: 624px; height: 162px;\">\n",
    "<pre><b>输入：</b>row = 2, col = 2, cells = [[1,1],[2,1],[1,2],[2,2]]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>上图描述了矩阵从第 0 天开始是如何变化的。\n",
    "可以从最上面一行到最下面一行的最后一天是第 2 天。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/07/27/2.png\" style=\"width: 504px; height: 178px;\">\n",
    "<pre><b>输入：</b>row = 2, col = 2, cells = [[1,1],[1,2],[2,1],[2,2]]\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>上图描述了矩阵从第 0 天开始是如何变化的。\n",
    "可以从最上面一行到最下面一行的最后一天是第 1 天。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/07/27/3.png\" style=\"width: 666px; height: 167px;\">\n",
    "<pre><b>输入：</b>row = 3, col = 3, cells = [[1,2],[2,1],[3,3],[2,2],[1,1],[1,3],[2,3],[3,2],[3,1]]\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>上图描述了矩阵从第 0 天开始是如何变化的。\n",
    "可以从最上面一行到最下面一行的最后一天是第 3 天。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= row, col &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>4 &lt;= row * col &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>cells.length == row * col</code></li>\n",
    "\t<li><code>1 &lt;= r<sub>i</sub> &lt;= row</code></li>\n",
    "\t<li><code>1 &lt;= c<sub>i</sub> &lt;= col</code></li>\n",
    "\t<li><code>cells</code>&nbsp;中的所有格子坐标都是 <strong>唯一</strong>&nbsp;的。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [last-day-where-you-can-still-cross](https://leetcode.cn/problems/last-day-where-you-can-still-cross/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [last-day-where-you-can-still-cross](https://leetcode.cn/problems/last-day-where-you-can-still-cross/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n2\\n[[1,1],[2,1],[1,2],[2,2]]', '2\\n2\\n[[1,1],[1,2],[2,1],[2,2]]', '3\\n3\\n[[1,2],[2,1],[3,3],[2,2],[1,1],[1,3],[2,3],[3,2],[3,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:\n",
    "        \n",
    "        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "        def canPass(n):\n",
    "            matrix = [[0] * col for _ in range(row)]\n",
    "            for i in range(n):\n",
    "                r, c = cells[i]\n",
    "                matrix[r-1][c-1] = 1\n",
    "            q = deque()\n",
    "            \n",
    "            for j in range(col):\n",
    "                if matrix[0][j] != 1:\n",
    "                    q.append((0, j))\n",
    "                    matrix[0][j] = -1\n",
    "            while q:\n",
    "                i, j = q.popleft()\n",
    "                for dx, dy in directions:\n",
    "                    newI = i + dx\n",
    "                    newJ = j + dy\n",
    "                    if 0 <= newI < row and 0 <= newJ < col and matrix[newI][newJ] == 0:\n",
    "                        if newI == row - 1:\n",
    "                            return True\n",
    "                        \n",
    "                        matrix[newI][newJ] = -1\n",
    "                        q.append((newI, newJ))\n",
    "            return False\n",
    "\n",
    "        l, r = 1, len(cells)\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if canPass(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, n: int, m: int, cells: List[List[int]]) -> int:\n",
    "        def find(x:int)->int:\n",
    "            while x!=fa[x]:\n",
    "                fa[x]=fa[fa[x]]\n",
    "                x=fa[x]\n",
    "            return x\n",
    "        fa=[_ for _ in range((n+1)*(m+1))]\n",
    "        for i in range(0,m):\n",
    "            fa[i]=0\n",
    "            fa[m*(n-1)+i]=m*(n-1)\n",
    "        dis=[[-1,0],[1,0],[0,-1],[0,1]]\n",
    "        vis=[[False]*(m+1) for _ in range(n+1)]\n",
    "        res=-1\n",
    "        for i in range(len(cells)-1,-1,-1):\n",
    "            x0,y0=cells[i][0]-1,cells[i][1]-1\n",
    "            vis[x0][y0]=1\n",
    "            for x,y in dis:\n",
    "                x1=x+x0\n",
    "                y1=y+y0\n",
    "                if x1>=0 and y1>=0 and x1<n and y1<m and vis[x1][y1]:\n",
    "                    fa1=find(x0*m+y0)\n",
    "                    fa2=find(x1*m+y1)\n",
    "                    fa[fa1]=fa2\n",
    "            if find(0)==find(m*(n-1)):\n",
    "                res=i\n",
    "                break\n",
    "        return res\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, n: int, m: int, cells: List[List[int]]) -> int:\n",
    "        def find(x:int)->int:\n",
    "            while x!=fa[x]:\n",
    "                fa[x]=fa[fa[x]]\n",
    "                x=fa[x]\n",
    "            return x\n",
    "        fa=[_ for _ in range((n+1)*(m+1))]\n",
    "        for i in range(0,m):\n",
    "            fa[i]=0\n",
    "            fa[m*(n-1)+i]=m*(n-1)\n",
    "        dis=[[-1,0],[1,0],[0,-1],[0,1]]\n",
    "        vis=[[False]*(m+1) for _ in range(n+1)]\n",
    "        res=-1\n",
    "        for i in range(len(cells)-1,-1,-1):\n",
    "            x0,y0=cells[i][0]-1,cells[i][1]-1\n",
    "            vis[x0][y0]=1\n",
    "            for x,y in dis:\n",
    "                x1=x+x0\n",
    "                y1=y+y0\n",
    "                if x1>=0 and y1>=0 and x1<n and y1<m and vis[x1][y1]:\n",
    "                    fa1=find(x0*m+y0)\n",
    "                    fa2=find(x1*m+y1)\n",
    "                    fa[fa1]=fa2\n",
    "            if find(0)==find(m*(n-1)):\n",
    "                res=i\n",
    "                break\n",
    "        return res\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:\n",
    "        def bfs(q,vis,G):\n",
    "            \n",
    "            while q:\n",
    "                x,y = q.pop(0)\n",
    "                if x==row-1:\n",
    "                    return True\n",
    "                for nx,ny in (x-1,y),(x+1,y),(x,y-1),(x,y+1):\n",
    "                    \n",
    "                    if 0<=nx<row and 0<=ny<col and G[nx][ny] == 0 and not vis[nx][ny]:\n",
    "                        vis[nx][ny] = True\n",
    "                        q.append((nx,ny))\n",
    "                    \n",
    "            return False\n",
    "        def check(day):\n",
    "            G = [[0]*col for _ in range(row)]\n",
    "            for i in range(day):\n",
    "                r,c = cells[i][0]-1,cells[i][1]-1\n",
    "                # print(r,c)\n",
    "                G[r][c] = 1\n",
    "            q = []\n",
    "            vis = [[False]*col for _ in range(row)]\n",
    "            for i in range(col):\n",
    "                if G[0][i] == 0:\n",
    "                    vis[0][i] = True\n",
    "                    q.append((0,i))\n",
    "            if bfs(q,vis,G):\n",
    "              return True\n",
    "            return False\n",
    "            \n",
    "            \n",
    "            \n",
    "\n",
    "        l = 0\n",
    "        r = row * col\n",
    "        while l < r:\n",
    "            mid = l + (r-l+1)//2\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r= mid-1\n",
    "        return l\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:\n",
    "        left, right, ans = 0, row * col, 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            \n",
    "            grid = [[1] * col for _ in range(row)]\n",
    "            for x, y in cells[:mid]:\n",
    "                grid[x - 1][y - 1] = 0\n",
    "\n",
    "            q = deque()\n",
    "            for i in range(col):\n",
    "                if grid[0][i]:\n",
    "                    q.append((0, i))\n",
    "                    grid[0][i] = 0\n",
    "            \n",
    "            found = False\n",
    "            while q:\n",
    "                x, y = q.popleft()\n",
    "                for nx, ny in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:\n",
    "                    if 0 <= nx < row and 0 <= ny < col and grid[nx][ny]:\n",
    "                        if nx == row - 1:\n",
    "                            found = True\n",
    "                            break\n",
    "                        q.append((nx, ny))\n",
    "                        grid[nx][ny] = 0\n",
    "            \n",
    "            if found:\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:\n",
    "        left, right= 0, row * col\n",
    "        dirs=[[-1,0],[0,1],[1,0],[0,-1]]\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            grid = [[1] * col for _ in range(row)]\n",
    "            for x, y in cells[:mid]:\n",
    "                grid[x - 1][y - 1] = 0\n",
    "            q = deque()\n",
    "            for i in range(col):\n",
    "                if grid[0][i]:\n",
    "                    q.append((0, i))\n",
    "                    grid[0][i] = 0\n",
    "            found = False\n",
    "            while q:\n",
    "                x, y = q.popleft()\n",
    "                for dx,dy in dirs:\n",
    "                    nx=x+dx\n",
    "                    ny=y+dy\n",
    "                    if 0 <= nx < row and 0 <= ny < col and grid[nx][ny]:\n",
    "                        if nx == row - 1:\n",
    "                            found = True\n",
    "                            break\n",
    "                        q.append((nx, ny))\n",
    "                        grid[nx][ny] = 0\n",
    "            if found:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:\n",
    "        father = [[0 for _ in range(col)] for _ in range(row)]\n",
    "        if row > 10000:\n",
    "            return 0\n",
    "        n = len(cells)\n",
    "        directions = [(-1,0),(1,0),(0,-1),(0,1)]\n",
    "        def mark_father(x,y,value):\n",
    "            q = [(x,y),]\n",
    "            while q:\n",
    "                now = q.pop(0)\n",
    "                for direction in directions:\n",
    "                    new_x = direction[0] + now[0]\n",
    "                    new_y = direction[1] + now[1]\n",
    "                    if new_x >= row or new_x < 0 or new_y >= col or new_y < 0:\n",
    "                        continue\n",
    "                    if father[new_x][new_y]:\n",
    "                        continue\n",
    "                    father[new_x][new_y] = value\n",
    "                    q.append((new_x,new_y))\n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            cells[i][0] -= 1\n",
    "            cells[i][1] -= 1\n",
    "            father[cells[i][0]][cells[i][1]] = -1\n",
    "        for i in range(col):\n",
    "            if not father[0][i]:\n",
    "                father[0][i] = 1\n",
    "                mark_father(0,i,1)\n",
    "            if not father[row-1][i]:\n",
    "                father[row-1][i] = 2\n",
    "                mark_father(row-1,i)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            x = cells[i][0]\n",
    "            y = cells[i][1]\n",
    "            up_flag = False\n",
    "            down_flag = False\n",
    "            wait_marks = []\n",
    "            for direction in directions:\n",
    "                new_x = direction[0] + x\n",
    "                new_y = direction[1] + y\n",
    "                if new_y >= col or new_y < 0:\n",
    "                    continue\n",
    "                if new_x < 0 or (new_x < row and father[new_x][new_y] == 1):\n",
    "                    father[x][y] = 1\n",
    "                    up_flag = True\n",
    "                if new_x >= row or (new_x >= 0 and father[new_x][new_y] == 2):\n",
    "                    father[x][y] = 2\n",
    "                    down_flag = True\n",
    "                if new_x >= 0 and new_x < row and not father[new_x][new_y]:\n",
    "                    wait_marks.append((new_x,new_y))                \n",
    "            if up_flag and down_flag:\n",
    "                return i\n",
    "            if not up_flag and not down_flag:\n",
    "                father[x][y] = 0\n",
    "            else:\n",
    "                for wait_mark in wait_marks:\n",
    "                    father[wait_mark[0]][wait_mark[1]] = father[x][y]\n",
    "                    mark_father(wait_mark[0],wait_mark[1],father[x][y])\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:\n",
    "        father = [[0 for _ in range(col)] for _ in range(row)]\n",
    "        n = len(cells)\n",
    "        directions = [(-1,0),(1,0),(0,-1),(0,1)]\n",
    "        def mark_father(x,y,value):\n",
    "            q = [(x,y),]\n",
    "            while q:\n",
    "                now = q.pop(0)\n",
    "                for direction in directions:\n",
    "                    new_x = direction[0] + now[0]\n",
    "                    new_y = direction[1] + now[1]\n",
    "                    if new_x >= row or new_x < 0 or new_y >= col or new_y < 0:\n",
    "                        continue\n",
    "                    if father[new_x][new_y]:\n",
    "                        continue\n",
    "                    father[new_x][new_y] = value\n",
    "                    q.append((new_x,new_y))\n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            cells[i][0] -= 1\n",
    "            cells[i][1] -= 1\n",
    "            father[cells[i][0]][cells[i][1]] = -1\n",
    "        for i in range(col):\n",
    "            if not father[0][i]:\n",
    "                father[0][i] = 1\n",
    "                mark_father(0,i,1)\n",
    "            if not father[row-1][i]:\n",
    "                father[row-1][i] = 2\n",
    "                mark_father(row-1,i)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            x = cells[i][0]\n",
    "            y = cells[i][1]\n",
    "            up_flag = False\n",
    "            down_flag = False\n",
    "            wait_mark = False\n",
    "            for direction in directions:\n",
    "                new_x = direction[0] + x\n",
    "                new_y = direction[1] + y\n",
    "                if new_y >= col or new_y < 0:\n",
    "                    continue\n",
    "                if new_x < 0 or (new_x < row and father[new_x][new_y] == 1):\n",
    "                    father[x][y] = 1\n",
    "                    up_flag = True\n",
    "                if new_x >= row or (new_x >= 0 and father[new_x][new_y] == 2):\n",
    "                    father[x][y] = 2\n",
    "                    down_flag = True\n",
    "                if new_x >= 0 and new_x < row and not father[new_x][new_y]:\n",
    "                    wait_mark = True        \n",
    "            if up_flag and down_flag:\n",
    "                return i\n",
    "            if not up_flag and not down_flag:\n",
    "                father[x][y] = 0\n",
    "            else:\n",
    "                if wait_mark:\n",
    "                    mark_father(x,y,father[x][y])\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:\n",
    "        father = [[0 for _ in range(col)] for _ in range(row)]\n",
    "        n = len(cells)\n",
    "        directions = ((-1,0),(1,0),(0,-1),(0,1))\n",
    "        q = deque()\n",
    "        def mark_father(x,y,value):\n",
    "            q.append((x,y))\n",
    "            while q:\n",
    "                now = q.popleft()\n",
    "                for direction in directions:\n",
    "                    new_x = direction[0] + now[0]\n",
    "                    new_y = direction[1] + now[1]\n",
    "                    if new_x >= row or new_x < 0 or new_y >= col or new_y < 0:\n",
    "                        continue\n",
    "                    if father[new_x][new_y]:\n",
    "                        continue\n",
    "                    father[new_x][new_y] = value\n",
    "                    q.append((new_x,new_y))\n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            cells[i][0] -= 1\n",
    "            cells[i][1] -= 1\n",
    "            father[cells[i][0]][cells[i][1]] = -1\n",
    "        for i in range(col):\n",
    "            if not father[0][i]:\n",
    "                father[0][i] = 1\n",
    "                mark_father(0,i,1)\n",
    "            if not father[row-1][i]:\n",
    "                father[row-1][i] = 2\n",
    "                mark_father(row-1,i)\n",
    "        up_flag = False\n",
    "        down_flag = False\n",
    "        wait_mark = False\n",
    "        x = 0\n",
    "        y = 0\n",
    "        new_x = 0\n",
    "        new_y = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            x = cells[i][0]\n",
    "            y = cells[i][1]\n",
    "            up_flag = False\n",
    "            down_flag = False\n",
    "            wait_mark = False\n",
    "            for direction in directions:\n",
    "                new_x = direction[0] + x\n",
    "                new_y = direction[1] + y\n",
    "                if new_y >= col or new_y < 0:\n",
    "                    continue\n",
    "                if new_x >= 0 and new_x < row:\n",
    "                    if not father[new_x][new_y]:\n",
    "                        wait_mark = True  \n",
    "                        continue\n",
    "                    if father[new_x][new_y] == 1:\n",
    "                        father[x][y] = 1\n",
    "                        up_flag = True\n",
    "                    if father[new_x][new_y] == 2:\n",
    "                        father[x][y] = 2\n",
    "                        down_flag = True\n",
    "                elif new_x < 0:\n",
    "                    father[x][y] = 1\n",
    "                    up_flag = True\n",
    "                elif new_x >= row:\n",
    "                    father[x][y] = 2\n",
    "                    down_flag = True\n",
    "            if up_flag and down_flag:\n",
    "                return i\n",
    "            if not up_flag and not down_flag:\n",
    "                father[x][y] = 0\n",
    "            else:\n",
    "                if wait_mark:\n",
    "                    mark_father(x,y,father[x][y])\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:\n",
    "        father = [[0 for _ in range(col)] for _ in range(row)]\n",
    "        n = len(cells)\n",
    "        directions = ((-1,0),(1,0),(0,-1),(0,1))\n",
    "        def mark_father(x,y,value):\n",
    "            q = [(x,y),]\n",
    "            while q:\n",
    "                now = q.pop(0)\n",
    "                for direction in directions:\n",
    "                    new_x = direction[0] + now[0]\n",
    "                    new_y = direction[1] + now[1]\n",
    "                    if new_x >= row or new_x < 0 or new_y >= col or new_y < 0:\n",
    "                        continue\n",
    "                    if father[new_x][new_y]:\n",
    "                        continue\n",
    "                    father[new_x][new_y] = value\n",
    "                    q.append((new_x,new_y))\n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            cells[i][0] -= 1\n",
    "            cells[i][1] -= 1\n",
    "            father[cells[i][0]][cells[i][1]] = -1\n",
    "        for i in range(col):\n",
    "            if not father[0][i]:\n",
    "                father[0][i] = 1\n",
    "                mark_father(0,i,1)\n",
    "            if not father[row-1][i]:\n",
    "                father[row-1][i] = 2\n",
    "                mark_father(row-1,i)\n",
    "        up_flag = False\n",
    "        down_flag = False\n",
    "        wait_mark = False\n",
    "        for i in range(n-1,-1,-1):\n",
    "            x = cells[i][0]\n",
    "            y = cells[i][1]\n",
    "            up_flag = False\n",
    "            down_flag = False\n",
    "            wait_mark = False\n",
    "            for direction in directions:\n",
    "                new_x = direction[0] + x\n",
    "                new_y = direction[1] + y\n",
    "                if new_y >= col or new_y < 0:\n",
    "                    continue\n",
    "                if new_x >= 0 and new_x < row:\n",
    "                    if not father[new_x][new_y]:\n",
    "                        wait_mark = True  \n",
    "                        continue\n",
    "                    if father[new_x][new_y] == 1:\n",
    "                        father[x][y] = 1\n",
    "                        up_flag = True\n",
    "                    if father[new_x][new_y] == 2:\n",
    "                        father[x][y] = 2\n",
    "                        down_flag = True\n",
    "                elif new_x < 0:\n",
    "                    father[x][y] = 1\n",
    "                    up_flag = True\n",
    "                elif new_x >= row:\n",
    "                    father[x][y] = 2\n",
    "                    down_flag = True\n",
    "            if up_flag and down_flag:\n",
    "                return i\n",
    "            if not up_flag and not down_flag:\n",
    "                father[x][y] = 0\n",
    "            else:\n",
    "                if wait_mark:\n",
    "                    mark_father(x,y,father[x][y])\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "m = 0\r\n",
    "n = 0\r\n",
    "parent = [0] * 20000\r\n",
    "neighbors = [(-1, 0), (1, 0), (0, -1), (0, 1)]\r\n",
    "\r\n",
    "def find(idx: int) -> int:\r\n",
    "    if parent[idx] != idx:\r\n",
    "        parent[idx] = find(parent[idx])\r\n",
    "    return parent[idx]\r\n",
    "\r\n",
    "def join(i1: int, j1: int, i2: int, j2: int) -> bool:\r\n",
    "    fidx = find(i1 * n + j1)\r\n",
    "    gidx = find(i2 * n + j2)\r\n",
    "    fi, fj = divmod(fidx, n)\r\n",
    "    gi, gj = divmod(gidx, n)\r\n",
    "    if ((fi == 0 and gi == m - 1) or (fi == m - 1 and gi == 0)):\r\n",
    "        return True\r\n",
    "\r\n",
    "    if fi != gi or fj != gj:\r\n",
    "        if gi == 0 or gi == m - 1:\r\n",
    "            parent[fi * n + fj] = gi * n + gj\r\n",
    "        else:\r\n",
    "            parent[gi * n + gj] = fi * n + fj\r\n",
    "\r\n",
    "    return False\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:\r\n",
    "        global m, n\r\n",
    "        m = row\r\n",
    "        n = col\r\n",
    "        board = [[1] * n for _ in range(m)]\r\n",
    "        for idx in range(m * n):\r\n",
    "            parent[idx] = idx\r\n",
    "\r\n",
    "        k = len(cells) - 1\r\n",
    "        while k >= 0:\r\n",
    "            i, j = cells[k]\r\n",
    "            i -= 1\r\n",
    "            j -= 1\r\n",
    "            board[i][j] = 0\r\n",
    "            for a, b in neighbors:\r\n",
    "                if 0 <= i + a < m and 0 <= j + b < n and board[i + a][j + b] == 0 and \\\r\n",
    "                    join(i, j, i + a, j + b):\r\n",
    "                    return k\r\n",
    "            k -= 1\r\n",
    "        \r\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:\n",
    "        father = [[0 for _ in range(col)] for _ in range(row)]\n",
    "        if col > 500:\n",
    "            return 0\n",
    "        n = len(cells)\n",
    "        directions = [(-1,0),(1,0),(0,-1),(0,1)]\n",
    "        def mark_father(x,y,value):\n",
    "            q = [(x,y),]\n",
    "            while q:\n",
    "                now = q.pop(0)\n",
    "                for direction in directions:\n",
    "                    new_x = direction[0] + now[0]\n",
    "                    new_y = direction[1] + now[1]\n",
    "                    if new_x >= row or new_x < 0 or new_y >= col or new_y < 0:\n",
    "                        continue\n",
    "                    if father[new_x][new_y]:\n",
    "                        continue\n",
    "                    father[new_x][new_y] = value\n",
    "                    q.append((new_x,new_y))\n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            cells[i][0] -= 1\n",
    "            cells[i][1] -= 1\n",
    "            father[cells[i][0]][cells[i][1]] = -1\n",
    "        for i in range(col):\n",
    "            if not father[0][i]:\n",
    "                father[0][i] = 1\n",
    "                mark_father(0,i,1)\n",
    "            if not father[row-1][i]:\n",
    "                father[row-1][i] = 2\n",
    "                mark_father(row-1,i)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            x = cells[i][0]\n",
    "            y = cells[i][1]\n",
    "            up_flag = False\n",
    "            down_flag = False\n",
    "            wait_marks = []\n",
    "            for direction in directions:\n",
    "                new_x = direction[0] + x\n",
    "                new_y = direction[1] + y\n",
    "                if new_y >= col or new_y < 0:\n",
    "                    continue\n",
    "                if new_x < 0 or (new_x < row and father[new_x][new_y] == 1):\n",
    "                    father[x][y] = 1\n",
    "                    up_flag = True\n",
    "                if new_x >= row or (new_x >= 0 and father[new_x][new_y] == 2):\n",
    "                    father[x][y] = 2\n",
    "                    down_flag = True\n",
    "                if new_x >= 0 and new_x < row and not father[new_x][new_y]:\n",
    "                    wait_marks.append((new_x,new_y))                \n",
    "            if up_flag and down_flag:\n",
    "                return i\n",
    "            if not up_flag and not down_flag:\n",
    "                father[x][y] = 0\n",
    "            else:\n",
    "                for wait_mark in wait_marks:\n",
    "                    father[wait_mark[0]][wait_mark[1]] = father[x][y]\n",
    "                    mark_father(wait_mark[0],wait_mark[1],father[x][y])\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:\n",
    "        father = [[-1 for _ in range(col)] for _ in range(row)]\n",
    "        n = len(cells)\n",
    "        directions = ((-1,0),(1,0),(0,-1),(0,1))\n",
    "        q = deque()\n",
    "        def mark_father(x,y,value):\n",
    "            q.append((x,y))\n",
    "            while q:\n",
    "                now = q.popleft()\n",
    "                for direction in directions:\n",
    "                    new_x = direction[0] + now[0]\n",
    "                    new_y = direction[1] + now[1]\n",
    "                    if new_x >= row or new_x < 0 or new_y >= col or new_y < 0:\n",
    "                        continue\n",
    "                    if father[new_x][new_y]:\n",
    "                        continue\n",
    "                    father[new_x][new_y] = value\n",
    "                    q.append((new_x,new_y))\n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            cells[i][0] -= 1\n",
    "            cells[i][1] -= 1\n",
    "        for i in range(col):\n",
    "            if not father[0][i]:\n",
    "                father[0][i] = 1\n",
    "                mark_father(0,i,1)\n",
    "            if not father[row-1][i]:\n",
    "                father[row-1][i] = 2\n",
    "                mark_father(row-1,i)\n",
    "        up_flag = False\n",
    "        down_flag = False\n",
    "        wait_mark = False\n",
    "        x = 0\n",
    "        y = 0\n",
    "        new_x = 0\n",
    "        new_y = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            x = cells[i][0]\n",
    "            y = cells[i][1]\n",
    "            up_flag = False\n",
    "            down_flag = False\n",
    "            wait_mark = False\n",
    "            for direction in directions:\n",
    "                new_x = direction[0] + x\n",
    "                new_y = direction[1] + y\n",
    "                if new_y >= col or new_y < 0:\n",
    "                    continue\n",
    "                if new_x >= 0 and new_x < row:\n",
    "                    if not father[new_x][new_y]:\n",
    "                        wait_mark = True  \n",
    "                        continue\n",
    "                    if father[new_x][new_y] == 1:\n",
    "                        father[x][y] = 1\n",
    "                        up_flag = True\n",
    "                    if father[new_x][new_y] == 2:\n",
    "                        father[x][y] = 2\n",
    "                        down_flag = True\n",
    "                elif new_x < 0:\n",
    "                    father[x][y] = 1\n",
    "                    up_flag = True\n",
    "                elif new_x >= row:\n",
    "                    father[x][y] = 2\n",
    "                    down_flag = True\n",
    "            if up_flag and down_flag:\n",
    "                return i\n",
    "            if not up_flag and not down_flag:\n",
    "                father[x][y] = 0\n",
    "            else:\n",
    "                if wait_mark:\n",
    "                    mark_father(x,y,father[x][y])\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:\n",
    "        father = [[0 for _ in range(col)] for _ in range(row)]\n",
    "        n = len(cells)\n",
    "        directions = ((-1,0),(1,0),(0,-1),(0,1))\n",
    "        q = deque()\n",
    "        def mark_father(x,y,value):\n",
    "            q.append((x,y))\n",
    "            while q:\n",
    "                now = q.popleft()\n",
    "                for direction in directions:\n",
    "                    new_x = direction[0] + now[0]\n",
    "                    new_y = direction[1] + now[1]\n",
    "                    if new_x >= row or new_x < 0 or new_y >= col or new_y < 0:\n",
    "                        continue\n",
    "                    if father[new_x][new_y]:\n",
    "                        continue\n",
    "                    father[new_x][new_y] = value\n",
    "                    q.append((new_x,new_y))\n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            cells[i][0] -= 1\n",
    "            cells[i][1] -= 1\n",
    "            father[cells[i][0]][cells[i][1]] = -1\n",
    "        for i in range(col):\n",
    "            if not father[0][i]:\n",
    "                father[0][i] = 1\n",
    "                mark_father(0,i,1)\n",
    "            if not father[row-1][i]:\n",
    "                father[row-1][i] = 2\n",
    "                mark_father(row-1,i)\n",
    "        up_flag = False\n",
    "        down_flag = False\n",
    "        wait_mark = False\n",
    "        x = 0\n",
    "        y = 0\n",
    "        new_x = 0\n",
    "        new_y = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            x = cells[i][0]\n",
    "            y = cells[i][1]\n",
    "            up_flag = False\n",
    "            down_flag = False\n",
    "            wait_mark = False\n",
    "            for direction in directions:\n",
    "                new_x = direction[0] + x\n",
    "                new_y = direction[1] + y\n",
    "                if new_y >= col or new_y < 0:\n",
    "                    continue\n",
    "                if new_x >= 0 and new_x < row:\n",
    "                    if not father[new_x][new_y]:\n",
    "                        wait_mark = True  \n",
    "                        continue\n",
    "                    if father[new_x][new_y] == 1:\n",
    "                        father[x][y] = 1\n",
    "                        up_flag = True\n",
    "                    if father[new_x][new_y] == 2:\n",
    "                        father[x][y] = 2\n",
    "                        down_flag = True\n",
    "                elif new_x < 0:\n",
    "                    father[x][y] = 1\n",
    "                    up_flag = True\n",
    "                elif new_x >= row:\n",
    "                    father[x][y] = 2\n",
    "                    down_flag = True\n",
    "            if up_flag and down_flag:\n",
    "                return i\n",
    "            if not up_flag and not down_flag:\n",
    "                father[x][y] = 0\n",
    "            else:\n",
    "                if wait_mark:\n",
    "                    mark_father(x,y,father[x][y])\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:\n",
    "        father = [[-1 for _ in range(col)] for _ in range(row)]\n",
    "        n = len(cells)\n",
    "        directions = ((-1,0),(1,0),(0,-1),(0,1))\n",
    "        q = deque()\n",
    "        def mark_father(x,y,value):\n",
    "            q.append((x,y))\n",
    "            while q:\n",
    "                now = q.popleft()\n",
    "                for direction in directions:\n",
    "                    new_x = direction[0] + now[0]\n",
    "                    new_y = direction[1] + now[1]\n",
    "                    if new_x >= row or new_x < 0 or new_y >= col or new_y < 0:\n",
    "                        continue\n",
    "                    if father[new_x][new_y]:\n",
    "                        continue\n",
    "                    father[new_x][new_y] = value\n",
    "                    q.append((new_x,new_y))\n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            cells[i][0] -= 1\n",
    "            cells[i][1] -= 1\n",
    "        for i in range(col):\n",
    "            if not father[0][i]:\n",
    "                father[0][i] = 1\n",
    "                mark_father(0,i,1)\n",
    "            if not father[row-1][i]:\n",
    "                father[row-1][i] = 2\n",
    "                mark_father(row-1,i)\n",
    "        up_flag = False\n",
    "        down_flag = False\n",
    "        wait_mark = False\n",
    "        x = 0\n",
    "        y = 0\n",
    "        new_x = 0\n",
    "        new_y = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            x = cells[i][0]\n",
    "            y = cells[i][1]\n",
    "            up_flag = False\n",
    "            down_flag = False\n",
    "            wait_mark = False\n",
    "            for direction in directions:\n",
    "                new_x = direction[0] + x\n",
    "                new_y = direction[1] + y\n",
    "                if new_y >= col or new_y < 0:\n",
    "                    continue\n",
    "                if new_x >= 0 and new_x < row:\n",
    "                    if not father[new_x][new_y]:\n",
    "                        wait_mark = True  \n",
    "                        continue\n",
    "                    if father[new_x][new_y] == 1:\n",
    "                        father[x][y] = 1\n",
    "                        up_flag = True\n",
    "                    if father[new_x][new_y] == 2:\n",
    "                        father[x][y] = 2\n",
    "                        down_flag = True\n",
    "                elif new_x < 0:\n",
    "                    father[x][y] = 1\n",
    "                    up_flag = True\n",
    "                elif new_x >= row:\n",
    "                    father[x][y] = 2\n",
    "                    down_flag = True\n",
    "            if up_flag and down_flag:\n",
    "                return i\n",
    "            if not up_flag and not down_flag:\n",
    "                father[x][y] = 0\n",
    "            elif wait_mark:\n",
    "                    mark_father(x,y,father[x][y])\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:\n",
    "        l, r, ans = 0, row * col, 0\n",
    "        while l < r:\n",
    "            mid = (l + r + 1) >> 1\n",
    "            grid = [[1] * col for _ in range(row)]\n",
    "            for x, y in cells[:mid]:\n",
    "                grid[x - 1][y - 1] = 0\n",
    "            q = deque()\n",
    "            for i in range(col):\n",
    "                if grid[0][i]:\n",
    "                    q.append((0, i))\n",
    "                    grid[0][i] = 0\n",
    "            \n",
    "            flag = False\n",
    "            while q:\n",
    "                x, y = q.popleft()\n",
    "                for nx, ny in (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1):\n",
    "                    if 0 <= nx < row and 0 <= ny < col and grid[nx][ny]:\n",
    "                        if nx == row - 1:\n",
    "                            flag = True\n",
    "                            break\n",
    "                        q.append((nx, ny))\n",
    "                        grid[nx][ny] = 0\n",
    "\n",
    "            if flag:\n",
    "                ans = mid\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:\n",
    "        father = [[-1 for _ in range(col)] for _ in range(row)]\n",
    "        n = len(cells)\n",
    "        directions = ((-1,0),(1,0),(0,-1),(0,1))\n",
    "        q = deque()\n",
    "        def mark_father(x,y,value):\n",
    "            q.append((x,y))\n",
    "            while q:\n",
    "                now = q.popleft()\n",
    "                for direction in directions:\n",
    "                    new_x = direction[0] + now[0]\n",
    "                    new_y = direction[1] + now[1]\n",
    "                    if new_x >= row or new_x < 0 or new_y >= col or new_y < 0:\n",
    "                        continue\n",
    "                    if father[new_x][new_y]:\n",
    "                        continue\n",
    "                    father[new_x][new_y] = value\n",
    "                    q.append((new_x,new_y))\n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            cells[i][0] -= 1\n",
    "            cells[i][1] -= 1\n",
    "        for i in range(col):\n",
    "            if not father[0][i]:\n",
    "                father[0][i] = 1\n",
    "                mark_father(0,i,1)\n",
    "            if not father[row-1][i]:\n",
    "                father[row-1][i] = 2\n",
    "                mark_father(row-1,i)\n",
    "        up_flag = False\n",
    "        down_flag = False\n",
    "        wait_mark = False\n",
    "        x = 0\n",
    "        y = 0\n",
    "        new_x = 0\n",
    "        new_y = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            x = cells[i][0]\n",
    "            y = cells[i][1]\n",
    "            up_flag = False\n",
    "            down_flag = False\n",
    "            wait_mark = False\n",
    "            for direction in directions:\n",
    "                new_x = direction[0] + x\n",
    "                new_y = direction[1] + y\n",
    "                if new_y >= col or new_y < 0:\n",
    "                    continue\n",
    "                if new_x >= 0 and new_x < row:\n",
    "                    if not father[new_x][new_y]:\n",
    "                        wait_mark = True  \n",
    "                        continue\n",
    "                    if father[new_x][new_y] == 1:\n",
    "                        father[x][y] = 1\n",
    "                        up_flag = True\n",
    "                    if father[new_x][new_y] == 2:\n",
    "                        father[x][y] = 2\n",
    "                        down_flag = True\n",
    "                elif new_x < 0:\n",
    "                    father[x][y] = 1\n",
    "                    up_flag = True\n",
    "                elif new_x >= row:\n",
    "                    father[x][y] = 2\n",
    "                    down_flag = True\n",
    "            if up_flag and down_flag:\n",
    "                return i\n",
    "            if not up_flag and not down_flag:\n",
    "                father[x][y] = 0\n",
    "            else:\n",
    "                if wait_mark:\n",
    "                    mark_father(x,y,father[x][y])\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:\n",
    "        father = [[0 for _ in range(col)] for _ in range(row)]\n",
    "        n = len(cells)\n",
    "        directions = ((-1,0),(1,0),(0,-1),(0,1))\n",
    "        def mark_father(x,y,value):\n",
    "            q = deque()\n",
    "            q.append((x,y))\n",
    "            while q:\n",
    "                now = q.popleft()\n",
    "                for direction in directions:\n",
    "                    new_x = direction[0] + now[0]\n",
    "                    new_y = direction[1] + now[1]\n",
    "                    if new_x >= row or new_x < 0 or new_y >= col or new_y < 0:\n",
    "                        continue\n",
    "                    if father[new_x][new_y]:\n",
    "                        continue\n",
    "                    father[new_x][new_y] = value\n",
    "                    q.append((new_x,new_y))\n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            cells[i][0] -= 1\n",
    "            cells[i][1] -= 1\n",
    "            father[cells[i][0]][cells[i][1]] = -1\n",
    "        for i in range(col):\n",
    "            if not father[0][i]:\n",
    "                father[0][i] = 1\n",
    "                mark_father(0,i,1)\n",
    "            if not father[row-1][i]:\n",
    "                father[row-1][i] = 2\n",
    "                mark_father(row-1,i)\n",
    "        up_flag = False\n",
    "        down_flag = False\n",
    "        wait_mark = False\n",
    "        for i in range(n-1,-1,-1):\n",
    "            x = cells[i][0]\n",
    "            y = cells[i][1]\n",
    "            up_flag = False\n",
    "            down_flag = False\n",
    "            wait_mark = False\n",
    "            for direction in directions:\n",
    "                new_x = direction[0] + x\n",
    "                new_y = direction[1] + y\n",
    "                if new_y >= col or new_y < 0:\n",
    "                    continue\n",
    "                if new_x >= 0 and new_x < row:\n",
    "                    if not father[new_x][new_y]:\n",
    "                        wait_mark = True  \n",
    "                        continue\n",
    "                    if father[new_x][new_y] == 1:\n",
    "                        father[x][y] = 1\n",
    "                        up_flag = True\n",
    "                    if father[new_x][new_y] == 2:\n",
    "                        father[x][y] = 2\n",
    "                        down_flag = True\n",
    "                elif new_x < 0:\n",
    "                    father[x][y] = 1\n",
    "                    up_flag = True\n",
    "                elif new_x >= row:\n",
    "                    father[x][y] = 2\n",
    "                    down_flag = True\n",
    "            if up_flag and down_flag:\n",
    "                return i\n",
    "            if not up_flag and not down_flag:\n",
    "                father[x][y] = 0\n",
    "            else:\n",
    "                if wait_mark:\n",
    "                    mark_father(x,y,father[x][y])\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "        n = len(cells)\n",
    "        low = 0\n",
    "        high = n+1\n",
    "\n",
    "        def find_way(visited):\n",
    "            bfs = deque([(0,y) for y in range(col) if visited[0][y]==0])\n",
    "            for y in range(col):\n",
    "                visited[0][y] = 1\n",
    "\n",
    "            while bfs:\n",
    "                x,y = bfs.popleft()\n",
    "                if x==row-1:\n",
    "                    return True\n",
    "                for dx,dy in [(x+1,y),(x,y-1),(x,y+1),(x-1,y)]:\n",
    "                    if 0<=dx<row and 0<=dy<col and visited[dx][dy] ==0:\n",
    "                        visited[dx][dy] = 1\n",
    "                        bfs.append((dx,dy))\n",
    "            return False \n",
    "                    \n",
    "\n",
    "        while low<high:\n",
    "            mid = (high+low)//2\n",
    "            visited = [[0]*col for _ in range(row)]\n",
    "            for i in range(mid):\n",
    "                x,y = cells[i]\n",
    "                visited[x-1][y-1] = 1\n",
    "\n",
    "            if find_way(visited):\n",
    "                low = mid+1\n",
    "            else:\n",
    "                high = mid \n",
    "        return low-1\n",
    "            \n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:\n",
    "        father = [[0 for _ in range(col)] for _ in range(row)]\n",
    "        n = len(cells)\n",
    "        directions = [(-1,0),(1,0),(0,-1),(0,1)]\n",
    "        def mark_father(x,y,value):\n",
    "            q = [(x,y),]\n",
    "            while q:\n",
    "                now = q.pop(0)\n",
    "                for direction in directions:\n",
    "                    new_x = direction[0] + now[0]\n",
    "                    new_y = direction[1] + now[1]\n",
    "                    if new_x >= row or new_x < 0 or new_y >= col or new_y < 0:\n",
    "                        continue\n",
    "                    if father[new_x][new_y]:\n",
    "                        continue\n",
    "                    father[new_x][new_y] = value\n",
    "                    q.append((new_x,new_y))\n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            cells[i][0] -= 1\n",
    "            cells[i][1] -= 1\n",
    "            father[cells[i][0]][cells[i][1]] = -1\n",
    "        for i in range(col):\n",
    "            if not father[0][i]:\n",
    "                father[0][i] = 1\n",
    "                mark_father(0,i,1)\n",
    "            if not father[row-1][i]:\n",
    "                father[row-1][i] = 2\n",
    "                mark_father(row-1,i)\n",
    "        up_flag = False\n",
    "        down_flag = False\n",
    "        wait_mark = False\n",
    "        for i in range(n-1,-1,-1):\n",
    "            x = cells[i][0]\n",
    "            y = cells[i][1]\n",
    "            up_flag = False\n",
    "            down_flag = False\n",
    "            wait_mark = False\n",
    "            for direction in directions:\n",
    "                new_x = direction[0] + x\n",
    "                new_y = direction[1] + y\n",
    "                if new_y >= col or new_y < 0:\n",
    "                    continue\n",
    "                if new_x >= 0 and new_x < row:\n",
    "                    if not father[new_x][new_y]:\n",
    "                        wait_mark = True  \n",
    "                        continue\n",
    "                    if father[new_x][new_y] == 1:\n",
    "                        father[x][y] = 1\n",
    "                        up_flag = True\n",
    "                    if father[new_x][new_y] == 2:\n",
    "                        father[x][y] = 2\n",
    "                        down_flag = True\n",
    "                elif new_x < 0:\n",
    "                    father[x][y] = 1\n",
    "                    up_flag = True\n",
    "                elif new_x >= row:\n",
    "                    father[x][y] = 2\n",
    "                    down_flag = True\n",
    "            if up_flag and down_flag:\n",
    "                return i\n",
    "            if not up_flag and not down_flag:\n",
    "                father[x][y] = 0\n",
    "            else:\n",
    "                if wait_mark:\n",
    "                    mark_father(x,y,father[x][y])\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DisjointSet:\n",
    "    \"\"\"\n",
    "    并查集\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self, size: int) -> None:\n",
    "        self.s = [i for i in range(size)]  # 使用数组映射,{索引:集合根},初始为自身,表示根就是它自己\n",
    "        self.size = [1 for _ in range(size)]  # 记录集合大小,初始为1,自身为一个集合\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        \"\"\"\n",
    "        查找集合的根\n",
    "        \"\"\"\n",
    "        if x == self.s[x]:  # 索引对应是自身的就是根\n",
    "            return x\n",
    "        # 路径压缩,在查找途中将根值赋值到集合里的元素上,加快下次查询\n",
    "        self.s[x] = self.find(self.s[x])\n",
    "        return self.s[x]\n",
    "\n",
    "    def union(self, x: int, y: int) -> None:\n",
    "        \"\"\"\n",
    "        合并两个集合\n",
    "        \"\"\"\n",
    "        rootX = self.find(x)  # 找到根进行合并\n",
    "        rootY = self.find(y)\n",
    "        if rootX == rootY:\n",
    "            return\n",
    "        # 按集合大小进行合并,小集合加入大集合\n",
    "        if self.size[rootX] < self.size[rootY]:\n",
    "            self.s[rootX] = rootY\n",
    "            self.size[rootY] += self.size[rootX]\n",
    "        else:\n",
    "            self.s[rootY] = rootX\n",
    "            self.size[rootX] += self.size[rootY]\n",
    "\n",
    "    def isConnect(self, x: int, y: int) -> bool:\n",
    "        \"\"\"\n",
    "        检查两个集合是否连通\n",
    "        \"\"\"\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.map = None\n",
    "        self.set = None\n",
    "\n",
    "    def latestDayToCross(self, row: int, col: int, cells: list[list[int]]) -> int:\n",
    "        self.map = [[False for _ in range(col)] for _ in range(row)]  # 是否为陆地\n",
    "        size = row * col\n",
    "        self.set = DisjointSet(size + 2)  # 并查集\n",
    "        up = size  # 上下超级节点\n",
    "        down = up + 1\n",
    "        for i in range(len(cells) - 1, -1, -1):  # 倒序,找陆地\n",
    "            r = cells[i][0] - 1  # 下标从1开始,需要减一\n",
    "            c = cells[i][1] - 1\n",
    "            self.map[r][c] = True\n",
    "            index = self.convert(col, r, c)  # 将二维坐标(r,c)转为一维坐标\n",
    "            self.search(row, col, r, c, index)  # 搜索四个方向,查看是否有陆地连通,若连通则合并陆地\n",
    "            if r == 0:  # 如果是最上面一行,与上超级节点连通\n",
    "                self.set.union(index, up)\n",
    "            elif r == row - 1:  # 如果是最下面一行,与下超级节点连通\n",
    "                self.set.union(index, down)\n",
    "            if self.set.isConnect(up, down):  # 检查上下是否连通\n",
    "                return i\n",
    "        return -1\n",
    "\n",
    "    def convert(self, col: int, r: int, c: int) -> int:\n",
    "        \"\"\"\n",
    "        二维坐标(r,c)转为一维坐标\n",
    "        \"\"\"\n",
    "        return r * col + c\n",
    "\n",
    "    def search(self, row: int, col: int, r: int, c: int, index: int) -> None:\n",
    "\n",
    "        directions = [[-1, 0], [0, -1], [1, 0], [0, 1]]\n",
    "        for dir in directions:\n",
    "            r2 = r + dir[0]\n",
    "            c2 = c + dir[1]\n",
    "            if self.isValid(r2, c2, row, col) and self.map[r2][c2]:  # 索引不越界且为陆地\n",
    "                index2 = self.convert(col, r2, c2)\n",
    "                self.set.union(index, index2)  # 连通\n",
    "\n",
    "    def isValid(self, r: int, c: int, row: int, col: int) -> bool:\n",
    "        return 0 <= r < row and 0 <= c < col"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.root = [i for i in range(n)]\n",
    "        self.size = [1] * n\n",
    "        self.part = n\n",
    "        return\n",
    "\n",
    "    def find(self, x):\n",
    "        lst = []\n",
    "        while x != self.root[x]:\n",
    "            lst.append(x)\n",
    "            # 在查询的时候合并到顺带直接根节点\n",
    "            x = self.root[x]\n",
    "        for w in lst:\n",
    "            self.root[w] = x\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] >= self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.root[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        # 将非根节点的秩赋0\n",
    "        self.size[root_x] = 0\n",
    "        self.part -= 1\n",
    "        return True\n",
    "\n",
    "    def is_connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def get_root_part(self):\n",
    "        # 获取每个根节点对应的组\n",
    "        part = defaultdict(list)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "\n",
    "    def get_root_size(self):\n",
    "        # 获取每个根节点对应的组大小\n",
    "        size = defaultdict(int)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            size[self.find(i)] = self.size[self.find(i)]\n",
    "        return size\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:\n",
    "        uf = UnionFind(row*col+2)\n",
    "        n = len(cells)\n",
    "        ans = -1\n",
    "        grid = [[1]*col for _ in range(row)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            x, y = cells[i]\n",
    "            x -= 1\n",
    "            y -= 1\n",
    "            grid[x][y] = 0\n",
    "            for a, b in [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]:\n",
    "                if 0<=a<row and 0<=b<col and grid[a][b] == 0:\n",
    "                    uf.union(x*col+y+1, a*col+b+1)\n",
    "            if x == 0:\n",
    "                uf.union(0, x*col+y+1)\n",
    "            if x == row-1:\n",
    "                uf.union(row*col+1, x * col + y + 1)\n",
    "            if uf.is_connected(0, row*col+1):\n",
    "                return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:\n",
    "        state = {}\n",
    "        for c in range(col + 2):\n",
    "            state[(0, c)] = 1\n",
    "            state[(row + 1, c)] = 2\n",
    "        dirs = (0, 1), (0, -1), (1, 0), (-1, 0)\n",
    "        for day, cell in enumerate(map(tuple, reversed(cells))):\n",
    "            m = 0\n",
    "            r, c = cell\n",
    "            for x, y in dirs:\n",
    "                temp = r + x, c + y\n",
    "                m |= state.get(temp, 0)\n",
    "            if m == 3:\n",
    "                return len(cells) - 1 - day\n",
    "            state[cell] = m\n",
    "            q = [cell]\n",
    "            while q:\n",
    "                r, c = q.pop(0)\n",
    "                for x, y in dirs:\n",
    "                    temp = r + x, c + y\n",
    "                    x = state.get(temp, 3)\n",
    "                    if x | m != x:\n",
    "                        state[temp] |= m\n",
    "                        q.append(temp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "direction = [-1, 0, 1, 0, -1]\n",
    "class Solution:\n",
    "    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:\n",
    "        m, n = row, col\n",
    "        cells = [[r - 1, c - 1] for r, c in cells]\n",
    "\n",
    "        def check(mid):\n",
    "            grid = [[0] * n for _ in range(m)]\n",
    "            for i in range(mid):\n",
    "                r, c = cells[i]\n",
    "                grid[r][c] = 1\n",
    "            q = deque([[0, j] for j in range(n) if grid[0][j] == 0])\n",
    "            for j in range(n):\n",
    "                grid[0][j] = 1\n",
    "            while q:\n",
    "                x, y = q.popleft()\n",
    "                for dx, dy in pairwise(direction):\n",
    "                    a, b = x + dx, y + dy\n",
    "                    if 0 <= a < m and 0 <= b < n and grid[a][b] == 0:\n",
    "                        if a == m - 1:\n",
    "                            return True\n",
    "                        grid[a][b] = 1\n",
    "                        q.append([a, b])\n",
    "\n",
    "            return False\n",
    "        \n",
    "        l, r = 1, m * n\n",
    "        return bisect_left(range(r + 1), 1, l, key=lambda t: not check(t)) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:\n",
    "\n",
    "        n, m = row, col \n",
    "        N = len(cells)\n",
    "        ma = defaultdict(int)\n",
    "        for i, (r,c) in enumerate(cells):\n",
    "            ma[(r-1,c-1)] = i + 1\n",
    "        def check(x):\n",
    "            if x >= N:\n",
    "                return False \n",
    "            Q = deque()\n",
    "            vis = [[0] * m for _ in range(n)]\n",
    "            for i in range(m):\n",
    "                if ma[(0, i)] > x:\n",
    "                    Q.append((0, i))\n",
    "                    vis[0][i] = 1\n",
    "            \n",
    "            while Q:\n",
    "                i, j = Q.popleft()\n",
    "                if i == n-1:\n",
    "                    return True \n",
    "\n",
    "                for [ni,nj] in [[i+1, j], [i-1, j], [i, j+1], [i, j-1]]:\n",
    "                    if 0<=ni<n and 0<=nj<m and ma[(ni,nj)] > x and not vis[ni][nj]:\n",
    "                        vis[ni][nj] = 1\n",
    "                        Q.append((ni,nj))\n",
    "            return False \n",
    "\n",
    "\n",
    "        l, r = 0, N\n",
    "        while l < r:\n",
    "            mid = (l + r + 1) >> 1\n",
    "            if check(mid):\n",
    "                l = mid \n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, m: int, n: int, cells: List[List[int]]) -> int:\n",
    "        p = [i for i in range(m * n + 2)]\n",
    "        \n",
    "        def find(x):\n",
    "            while p[x] != x:\n",
    "                p[x] = x = p[p[x]]\n",
    "            return x\n",
    "        \n",
    "        def checkAndUnion(i, j):\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "            if i == 0:\n",
    "                p[find(i * n + j)] = find(m * n)\n",
    "            if i == m - 1:\n",
    "                p[find(i * n + j)] = find(m * n + 1)\n",
    "        \n",
    "        valid = set()\n",
    "        for i in range(m * n - 1, -1, -1):\n",
    "            x, y = cells[i]\n",
    "            checkAndUnion(x, y)\n",
    "            valid.add((x, y))\n",
    "            for dx, dy in ((-1, 0), (1, 0), (0, 1), (0, -1)):\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 1 <= nx <= m and 1 <= ny <= n and (nx, ny) in valid:\n",
    "                    p[find(nx * n + ny - n - 1)] = find(x * n + y - n - 1)\n",
    "            if find(m * n) == find(m * n + 1):\n",
    "                return i\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, x) -> None:\n",
    "        self.uf = [-1] * x\n",
    "\n",
    "    def find(self, x):\n",
    "        r = x\n",
    "        while self.uf[x] >= 0:\n",
    "            x = self.uf[x]\n",
    "\n",
    "        while r != x:\n",
    "            self.uf[r], r = x, self.uf[r]\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        ux, uy = self.find(x), self.find(y)\n",
    "        if ux == uy:\n",
    "            return\n",
    "        if self.uf[ux] >= self.uf[uy]:\n",
    "            self.uf[uy] += self.uf[ux]\n",
    "            self.uf[ux] = uy\n",
    "        else:\n",
    "            self.uf[ux] += self.uf[uy]\n",
    "            self.uf[uy] = ux\n",
    "        return\n",
    "\n",
    "    def count(self):\n",
    "        ans = 0\n",
    "        for c in self.uf:\n",
    "            if c < 0 and c != -1:\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "    def valid(self):\n",
    "        n = len(self.uf)\n",
    "        for c in range(n):\n",
    "            if self.uf[c] == -n:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "    def __print__(self):\n",
    "        return self.uf\n",
    "    \n",
    "class Solution:\n",
    "    def latestDayToCross(self, n: int, m: int, cells: List[List[int]]) -> int:\n",
    "        uf = UnionFind(n * m + 2)\n",
    "        for i in range(m):\n",
    "            uf.union(n * m,i)\n",
    "        for i in range(m):\n",
    "            uf.union(n * m + 1,(n - 1) * m + i)\n",
    "        \n",
    "        vis = set()\n",
    "        for i in range(n * m - 1,-1,-1):\n",
    "            x,y = cells[i]\n",
    "            x -= 1\n",
    "            y -= 1\n",
    "            for dx,dy in [(1,0),(0,1),(-1,0),(0,-1)]:\n",
    "                nx,ny = x + dx,y + dy\n",
    "                if (nx,ny) in vis:\n",
    "                    uf.union(x * m + y,nx * m + ny)\n",
    "            vis.add((x,y))\n",
    "            if uf.find(n * m) == uf.find(n * m + 1):\n",
    "                return i\n",
    "        return 0\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, m: int, n: int, cells: List[List[int]]) -> int:\n",
    "        p = [i for i in range(m * n + 2)]\n",
    "        \n",
    "        def find(x):\n",
    "            while p[x] != x:\n",
    "                p[x] = x = p[p[x]]\n",
    "            return x\n",
    "        \n",
    "        def checkAndUnion(i, j):\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "            if i == 0:\n",
    "                p[find(i * n + j)] = find(m * n)\n",
    "            if i == m - 1:\n",
    "                p[find(i * n + j)] = find(m * n + 1)\n",
    "        \n",
    "        valid = set()\n",
    "        for i in range(m * n - 1, -1, -1):\n",
    "            x, y = cells[i]\n",
    "            checkAndUnion(x, y)\n",
    "            valid.add((x, y))\n",
    "            for dx, dy in ((-1, 0), (1, 0), (0, 1), (0, -1)):\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 1 <= nx <= m and 1 <= ny <= n and (nx, ny) in valid:\n",
    "                    p[find(nx * n + ny - n - 1)] = find(x * n + y - n - 1)\n",
    "            if find(m * n) == find(m * n + 1):\n",
    "                return i\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, m: int, n: int, cells: List[List[int]]) -> int:\n",
    "        p = [i for i in range(m * n + 2)]\n",
    "        \n",
    "        def find(x):\n",
    "            while p[x] != x:\n",
    "                p[x] = x = p[p[x]]\n",
    "            return x\n",
    "        \n",
    "        def checkAndUnion(i, j):\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "            if i == 0:\n",
    "                p[find(i * n + j)] = find(m * n)\n",
    "            if i == m - 1:\n",
    "                p[find(i * n + j)] = find(m * n + 1)\n",
    "        \n",
    "        valid = set()\n",
    "        for i in range(m * n - 1, -1, -1):\n",
    "            x, y = cells[i]\n",
    "            checkAndUnion(x, y)\n",
    "            valid.add((x, y))\n",
    "            for dx, dy in ((-1, 0), (1, 0), (0, 1), (0, -1)):\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 1 <= nx <= m and 1 <= ny <= n and (nx, ny) in valid:\n",
    "                    p[find(nx * n + ny - n - 1)] = find(x * n + y - n - 1)\n",
    "            if find(m * n) == find(m * n + 1):\n",
    "                return i\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:\n",
    "        l, r = 0, len(cells)\n",
    "        def check(mid):\n",
    "            grid = [[0] * col for _ in range(row)]\n",
    "            for a, b in cells[:mid]:\n",
    "                grid[a - 1][b - 1] = 1\n",
    "            q = deque()\n",
    "            for i in range(col):\n",
    "                if grid[0][i] == 0:\n",
    "                    q.append((0, i))\n",
    "            vis = set()\n",
    "            while q:\n",
    "                a, b = q.popleft()\n",
    "                if (a, b) in vis: continue\n",
    "                vis.add((a, b))\n",
    "                for x, y in (a, b + 1), (a + 1, b), (a, b - 1), (a - 1, b):\n",
    "                    if 0 <= x < row and 0 <= y < col and grid[x][y] == 0:\n",
    "                        if x == row - 1: return True\n",
    "                        q.append((x, y))\n",
    "            return False\n",
    "        while l < r:\n",
    "            mid = l + r + 1 >> 1\n",
    "            if check(mid): l = mid\n",
    "            else: r = mid - 1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, m: int, n: int, cells: List[List[int]]) -> int:\n",
    "        f = [[0] * n for _ in range(m)]\n",
    "        for i, [x, y] in enumerate(cells):\n",
    "            # print(x - 1, y - 1)\n",
    "            f[x - 1][y - 1] = i + 1\n",
    "        # print(f)\n",
    "        def check(mid):\n",
    "            # init\n",
    "            q = deque()\n",
    "            vis = set()\n",
    "            for i in range(n):\n",
    "                if f[0][i] > mid:\n",
    "                    q.append((0, i))\n",
    "                    vis.add((0, i))\n",
    "            while q:\n",
    "                x, y = q.popleft()\n",
    "                if x == m - 1:\n",
    "                    return True\n",
    "                for dx, dy in [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]]:\n",
    "                    if 0 <= dx < m and 0 <= dy < n and (dx, dy) not in vis and f[dx][dy] > mid:\n",
    "                        vis.add((dx, dy))\n",
    "                        q.append((dx, dy))\n",
    "            return False\n",
    "        l, r = 0, m * n\n",
    "        while l < r:\n",
    "            mid = (l + r + 1) // 2\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:\n",
    "        g = [[0] * col for _ in range(row)]\n",
    "        for i, (x, y) in enumerate(cells):\n",
    "            g[x-1][y-1] = i+1\n",
    "            \n",
    "        def bfs(day):\n",
    "            q = []\n",
    "            vis = set()\n",
    "            for j in range(col):\n",
    "                if g[0][j] > day:\n",
    "                    q.append((0, j))\n",
    "                    vis.add((0, j))\n",
    "            while q:\n",
    "                tmp, q = q, []\n",
    "                for i, j in tmp:\n",
    "                    if i == row - 1:\n",
    "                        return True\n",
    "                    for x, y in (i-1, j),(i+1,j),(i,j-1),(i,j+1):\n",
    "                        if 0<=x<row and 0<=y<col and (x, y) not in vis and g[x][y] > day:\n",
    "                                q.append((x, y))\n",
    "                                vis.add((x, y))\n",
    "            return False\n",
    "        \n",
    "        l, r = -1, row * col + 1\n",
    "        while l + 1 < r:\n",
    "            m = (l + r) // 2\n",
    "            if bfs(m):\n",
    "                l = m\n",
    "            else:\n",
    "                r = m\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:\n",
    "        ground = [[row*col]*col for _ in range(row)]\n",
    "        for i, e in enumerate(cells):\n",
    "            ground[e[0]-1][e[1]-1] = i\n",
    "        def fun(day):\n",
    "            q = deque([(0, i) for i in range(col) if day <= ground[0][i]])\n",
    "            visit = set(q)\n",
    "            while q:\n",
    "                x, y = q.popleft()\n",
    "                if x == row-1:\n",
    "                    return True\n",
    "                for a, b in [(x, y+1), (x, y-1), (x-1, y), (x+1, y)]:\n",
    "                    if 0 <= a < row and 0 <= b < col and (a, b) not in visit and day <= ground[a][b]:\n",
    "                        visit.add((a, b))\n",
    "                        q.append((a, b))\n",
    "            return False\n",
    "        left, right = 0, row*col\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) // 2\n",
    "            if fun(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid-1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:\n",
    "        def find(x):\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(x, y):\n",
    "            u, v = find(x), find(y)\n",
    "            fa[u] = v\n",
    "        def is_connected(x, y):\n",
    "            return find(x) == find(y)\n",
    "        fa = [i for i in range(row * col + 2)]\n",
    "        l, r = row * col, row * col + 1 # 作为上下界标记\n",
    "        s = set() # 存储已经有的节点\n",
    "        cells = [(x - 1, y - 1) for x, y in cells]\n",
    "        for k in range(row * col - 1, -1, -1):\n",
    "            if is_connected(l, r):\n",
    "                return k + 1\n",
    "            x, y = cells[k]\n",
    "            for nx, ny in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                if 0 <= nx < row and 0 <= ny < col and (nx, ny) in s:\n",
    "                    merge(x * col + y, nx * col + ny)\n",
    "            if x == 0:\n",
    "                merge(x * col + y, l)\n",
    "            if x == row - 1:\n",
    "                merge(x * col + y, r)\n",
    "            s.add((x, y))\n",
    "        \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:\n",
    "        p={i:i for i in range(row*col+2)}\n",
    "        c=row*col\n",
    "        f=row*col+1\n",
    "    \n",
    "        def find(x):\n",
    "            if p[x]==x:\n",
    "                return x\n",
    "            p[x]=find(p[x])\n",
    "            return p[x]\n",
    "\n",
    "        def union(x,y):\n",
    "            p[find(x)]=find(y)\n",
    "        s=set()\n",
    "        for i in range(len(cells)-1,-1,-1):\n",
    "            x=cells[i][0]-1\n",
    "            y=cells[i][1]-1\n",
    "        \n",
    "            if x==0:\n",
    "                union(x*col+y,c)\n",
    "                \n",
    "            if x+1==row:\n",
    "                union(x*col+y,f)\n",
    "\n",
    "            for x1,y1 in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:\n",
    "                if 0<=x1<row and 0<=y1<col and (x1,y1) in s:\n",
    "                    union(x*col+y,x1*col+y1)\n",
    "            s.add((x,y))\n",
    "           # print(s)\n",
    "          #  print(p)\n",
    "            if find(c)==find(f):\n",
    "\n",
    "                return i\n",
    "            \n",
    "           \n",
    "        \n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:\n",
    "        cells = [[y - 1 for y in x] for x in cells]\n",
    "        left = 0\n",
    "        right = len(cells)\n",
    "        while right > left + 1:\n",
    "            # print(left, right)\n",
    "            mid = (left + right) // 2\n",
    "            canWalkThrough = self.canWalkThrough(row, col, cells[:mid])\n",
    "            if canWalkThrough:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "\n",
    "        # print(left, right)\n",
    "        if self.canWalkThrough(row, col, cells[:right]):\n",
    "            return right\n",
    "        return left\n",
    "\n",
    "    def canWalkThrough(self, row, col, cells):\n",
    "        mat = [[0 for _ in range(col)] for _ in range(row)]\n",
    "        for i, j in cells:\n",
    "            mat[i][j] = 1\n",
    "\n",
    "        # print(cells, mat)\n",
    "\n",
    "        nodes = [(0, x) for x in range(col) if mat[0][x] == 0]\n",
    "        visited = set()\n",
    "        while nodes:\n",
    "            i, j = nodes.pop()\n",
    "            # print(i, j)\n",
    "            visited.add((i, j))\n",
    "            if i == row - 1:\n",
    "                return True\n",
    "            for newi, newj in [(i + 1, j), (i - 1, j), (i, j - 1), (i, j + 1)]:\n",
    "                if (newi, newj) not in visited and newi >= 0 and newi < row and newj >= 0 and newj < col and mat[newi][newj] == 0:\n",
    "                    nodes.append((newi, newj))\n",
    "                \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:\n",
    "\n",
    "        direction = [[0,1],[1,0],[-1,0],[0,-1],[1,1],[1,-1],[-1,1],[-1,-1]]\n",
    "\n",
    "        sizes = defaultdict(set)\n",
    "\n",
    "        def getPos(i,j):\n",
    "            return i * col + j\n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                sizes[getPos(i,j)].add(j)\n",
    "\n",
    "        parents = list(range(row*col))\n",
    "    \n",
    "        def find(x):\n",
    "            if x != parents[x]:\n",
    "                parents[x] = find(parents[x])\n",
    "            return parents[x]\n",
    "\n",
    "        def union(u,v):\n",
    "            x , y = find(u) , find(v)\n",
    "            if x != y:\n",
    "                parents[x] = y\n",
    "                sizes[y] |= sizes[x]\n",
    "\n",
    "        visited = set()\n",
    "        for i , (r , c) in enumerate(cells):\n",
    "            r -= 1\n",
    "            c -= 1\n",
    "            visited.add((r,c))\n",
    "            for dr , dc in direction:\n",
    "                nr , nc = r + dr , c + dc\n",
    "                if 0 <= nr < row and 0 <= nc < col and (nr,nc) in visited:\n",
    "                    union(getPos(r,c),getPos(nr,nc))\n",
    "                    z = find(getPos(r,c))\n",
    "                    if len(sizes[z]) == col:return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:\n",
    "        n = len(cells)\n",
    "        def get_idx(r: int, c: int) -> int:\n",
    "            return r * col + c\n",
    "        def connected(d: int) -> bool:\n",
    "            f = [i for i in range(n)]\n",
    "            def find(i: int) -> int:\n",
    "                if f[i] == i:\n",
    "                    return i\n",
    "                f[i] = find(f[i])\n",
    "                return f[i]\n",
    "            water = set(map(tuple, cells[: d]))\n",
    "            for r in range(row):\n",
    "                for c in range(col):\n",
    "                    if (r + 1, c + 1) in water:\n",
    "                        continue\n",
    "                    idx = get_idx(r, c)\n",
    "                    for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]:\n",
    "                        nr, nc = r + dr, c + dc\n",
    "                        if (not (0 <= nr < row and 0 <= nc < col)) or (nr + 1, nc + 1) in water:\n",
    "                            continue\n",
    "                        nidx = get_idx(nr, nc)\n",
    "                        if find(idx) != find(nidx):\n",
    "                            if f[idx] < f[nidx]:\n",
    "                                f[f[nidx]] = f[idx]\n",
    "                            else:\n",
    "                                f[f[idx]] = f[nidx]\n",
    "            return any(f[get_idx(row - 1, c)] < col for c in range(col))\n",
    "\n",
    "        l, r = 0, n\n",
    "        while l < r:\n",
    "            m = l + r + 1 >> 1\n",
    "            if connected(m):\n",
    "                l = m\n",
    "            else:\n",
    "                r = m - 1\n",
    "        return l"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
